Leetcode 2542

The apporach is simple, we want sum to be as big as possible, but more importantly our nums2(min) has to be bigger because it grows faster.

So we sort by nums2 at each index, we want to have our nums2 to be at max

we add all k item into the priority queue, and once we got the score, we want to make sure our score is actually good, so we want to keep going on nums2, while we polls the smallest from the nums1 and keep update items.

class Solution {
    public long maxScore(int[] nums1, int[] nums2, int k) {
        // we want nums2 be as big as possible 
        int n = nums1.length;
        int[][] pairs = new int[n][2];
        for(int i = 0; i < n; i ++){
            pairs[i] = new int[]{nums1[i],nums2[i]};
        }
        Arrays.sort(pairs,(a,b) -> b[1] - a[1]); // we want to sort the pair by biggest in nums2
        PriorityQueue<Integer> pq = new PriorityQueue<>(k,(a,b) -> a - b);
        
        long topK = 0;
        for(int i = 0; i < k; i ++){
            topK += pairs[i][0];
            pq.add(pairs[i][0]);
        }
        // score 
        long res = topK * pairs[k - 1][1];

        // slide all possiblity
        for(int i = k; i < n; i ++){
            topK += pairs[i][0] - pq.poll();
            pq.add(pairs[i][0]);

            res = Math.max(res,topK * pairs[i][1]);
        }
        return res;
    }
}